|
In computing and graph theory, a dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph. The set ''V'' of vertices of the graph is fixed, but the set ''E'' of edges can change. The three cases, in order of difficulty, are: * Edges are only added to the graph (this can be called ''incremental connectivity''); * Edges are only deleted from the graph (this can be called ''decremental connectivity''); * Edges can be either added or deleted (this can be called ''fully dynamic connectivity''). After each addition/deletion of an edge, the dynamic connectivity structure should adapt itself such that it can give quick answers to queries of the form "is there a path between ''x'' and ''y''?" (equivalently: "do vertices ''x'' and ''y'' belong to the same connected component?"). == Incremental connectivity == If edges can only be added, then the dynamic connectivity problem can be solved by a Disjoint-set data structure. Each set represents a connected component; there is a path between ''x'' and ''y'' if and only if they belong to the same set. The amortized time per operation is , where ''n'' is the number of vertices and α is the inverse Ackermann function, which is nearly constant. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Dynamic connectivity」の詳細全文を読む スポンサード リンク
|